package com.jp.algorithm.tier;

import org.omg.Messaging.SYNC_WITH_TRANSPORT;

import java.util.ArrayList;
import java.util.List;

public class Tier {

    Node root;
    public  Tier(){
        root = new Node(' ',false);
    }

    class Node{
        List<Node> list;
        Character c;
        Boolean isEnd;
        public Node(Character c,Boolean isEnd){
            this.c = c;
            this.list = new ArrayList<>();
            this.isEnd=isEnd;
        }
    }

    public void add(String str){
        Node cur = root;
        int index=0;
        while(index < str.length()){
            char childC = str.charAt(index);
            int i=0;
            boolean found=false;
            for(;i<cur.list.size(); i++){
                Node childNode = cur.list.get(i);
                if(childNode.c.equals(childC)){
                    cur=childNode;
                    index++;
                    found=true;
                    break;
                }
            }
            //子节点没找到
            if(found==false){
                Node newChild=null;
                if(index == str.length()-1)
                    newChild = new Node(childC,true);
                else{
                    newChild = new Node(childC,false);
                }
                cur.list.add(newChild);
                cur=newChild;
                index++;
            }
        }
    }

    public void print(Node node){
        System.out.println(node.c);
        for(Node n :node.list){
            print(n);
        }
    }

    public boolean search(String str){
        Node cur = root;
        int i=0;
        for(;i<str.length();i++){
            char tmpC = str.charAt(i);
            boolean found=false;
            for(Node n : cur.list){
                if(n.c.equals(tmpC)){
                    cur=n;
                    found=true;
                    break;
                }
            }
            if(!found) {
                return false;
            }
        }

        if(cur.isEnd){
            return true;
        }
        return false;
    }


    public static void testAdd(){
        Tier tier = new Tier();
        tier.add("A");
        tier.add("t");
        tier.add("te");
        tier.add("tea");
        tier.add("ted");
        tier.print(tier.root);
    }

    public static void testSearch(){
        Tier tier = new Tier();
        tier.add("A");
        tier.add("t");
        tier.add("te");
        tier.add("tea");
        tier.add("ted");
        System.out.println(tier.search("ta"));
    }

    public static void main(String[] args) {
        //testAdd();
        testSearch();
    }

}
